
//#include <assert.h>
//#include <iostream>
#include "PageCache.h"

PageCache* PageCache::m_pageCache = new PageCache;

//获取一个k页的span
Span* PageCache::NewSpan(size_t k)
{
	//assert(k > 0 && k < NPAGES);
	assert(k > 0 && k <= NPAGES);

	//当k为129时（大于128，为最大页数，直接找堆要）
	if (k > NPAGES - 1) //(k == NPAGES)
	{
		void* ptr = SystemAlloc(k);
		Span* span = m_spanPool.New();
		span->pageId = (size_t)ptr >> PAGE_SHIFT;
		span->n = k;
		m_idSpanMap[span->pageId] = span;
		return span;
	}

	//如果第k个桶里有span
	if (!m_spanList[k].Empty())
	{
		//拿到链表表头
		Span* KSpan = m_spanList[k].PopFront();

		//建立id和span的映射关系方便centralcache回收小块内存时查找对应的span
		for (size_t i = 0; i < KSpan->n; ++i)
		{
			m_idSpanMap[KSpan->pageId + i] = KSpan;
		}

		return KSpan;
	}


	//第k个桶里是空的,检测后面的桶里有没有span,如果有进行切分
	//切分成一个k页的span和一个 n-k 页的span
	//k页的span返回给central cache,n-k 页的span挂到第 n-k 号桶中去
	for (size_t i = k; i < NPAGES; ++i)
	{
		if (!m_spanList[i].Empty())
		{
			Span* nSpan = m_spanList[i].PopFront();

			Span* KSpan =  m_spanPool.New();
			//Span* KSpan = new Span;

			//在nSpan的头部切下K页
			//k页span返回，nSpan再挂到对应映射
			KSpan->pageId = nSpan->pageId;

			//更改页号
			KSpan->n = k;
			// std::cout << "KSpan->n " << KSpan->n << std::endl;
			nSpan->pageId += k;
			// std::cout << "nSpan->pageId += k " << nSpan->pageId << std::endl;
			nSpan->n -= k;
			// std::cout << "nSpan->n -= k " << nSpan->n << std::endl;

			m_spanList[nSpan->n].PushFront(nSpan); //把剩余的页挂到对应的位置

			//存储nSpan的首尾页号跟span映射,方便page cache回收内存时进行合并查找
			// std::cout << "=======================================" << std::endl;
			// std::cout << "nSpan->pageId " << nSpan->pageId << std::endl;
			// std::cout << "nSpan->n - 1 " << nSpan->n - 1 << std::endl;
			// std::cout << "nSpan->pageId + nSpan->n - 1 " << nSpan->pageId + nSpan->n - 1 << std::endl;
			m_idSpanMap[nSpan->pageId] = nSpan;
			m_idSpanMap[nSpan->pageId + nSpan->n - 1] = nSpan;

			//建立id和span的映射，方便central cache回收查找对应的span
			// std::cout << "=======================================" << std::endl;
			for (size_t i = 0; i < KSpan->n; ++i)  //将内存分为k个页
			{
				// std::cout << "KSpan->pageId + i " << KSpan->pageId + i << std::endl;
				m_idSpanMap[KSpan->pageId + i] = KSpan;  
			}

			return KSpan;
		}
	}


	//如果没有能够分配的span，找堆在第128页开辟一个span
	Span* bigSpan =  m_spanPool.New();
	//Span* bigSpan = new Span;
	void* ptr = SystemAlloc(NPAGES - 1);
	bigSpan->pageId = (size_t)ptr >> PAGE_SHIFT;

	bigSpan->n = NPAGES - 1;
	m_spanList[bigSpan->n].PushFront(bigSpan);

	//递归
	return NewSpan(k);
}


//获取对象到span的映射
Span* PageCache::MapObjectToSpan(void* obj)
{
	size_t id = ((size_t)obj >> PAGE_SHIFT); //还原页号
	
	std::unique_lock<std::mutex> lock(m_pageMtx);
	auto ret = m_idSpanMap.find(id);

	if (ret != m_idSpanMap.end())
	{
		return ret->second;	//返回Span指针
	}

	assert(false);
	return nullptr;
}

//释放空闲span,合并相邻的span
void PageCache::ReleaseSpanToPageCache(Span* span)
{
	//大于128页的直接还给堆
	if (span->n > NPAGES - 1)
	{
		void* ptr = (void*)(span->pageId << PAGE_SHIFT);  //还原指针
		SystemFree(ptr, span->n);	//释放堆区内存
		m_spanPool.Delete(span);
		return;
	}

	//对span前后的页进行合并，解决内存碎片问题

	//向前合并
	while (true)
	{
		size_t prevId = span->pageId - 1;
		auto ret = m_idSpanMap.find(prevId);

		if(ret == m_idSpanMap.end())
		{
			break;  //如果前面没有页号，就不合并
		}

		Span* prevSpan = ret->second;

		if (prevSpan->isUsed == true)  //如果前面的页在使用，则不合并
		{
			break;
		}

		if (prevSpan->n + span->n > NPAGES - 1)  //如果合并起来的页大于128，无法管理
		{
			break;
		}

		//合并
		//std::cout << "span->n " << span->n << std::endl;
		//std::cout << "prevSpan->n " << prevSpan->n << std::endl;
		span->pageId = prevSpan->pageId;
		span->n += prevSpan->n;						//span->n += 1 ???
		m_spanList[prevSpan->n].Erase(prevSpan);	//??
		//std::cout << "prevSpan" << prevSpan << std::endl;
		//std::cout << "prevSpan next " << prevSpan->next << std::endl;
		//std::cout << "prevSpan prev " << prevSpan->prev << std::endl;

		m_spanPool.Delete(prevSpan);
	}

	//向后合并
	while (1)
	{
		size_t nextId = span->pageId + span->n;
		auto ret = m_idSpanMap.find(nextId);
		if (ret == m_idSpanMap.end())
		{
			break;
		}

		Span* nextSpan = ret->second;
		if (nextSpan->isUsed == true)
		{
			break;
		}
		if (nextSpan->n + span->n > NPAGES - 1)
		{
			break;
		}

		span->n += nextSpan->n;
		m_spanList[nextSpan->n].Erase(nextSpan);
		m_spanPool.Delete(nextSpan);
	}

	//将合并好后的页挂到相应的桶上
	m_spanList[span->n].PushFront(span);
	span->isUsed = false;

	//和并map里的数据
	m_idSpanMap[span->pageId] = span;
	m_idSpanMap[span->pageId + span->n - 1] = span;
}


void PageCache::testPrintSpanMap()
{
	std::cout << "m_idSpanMap.size(): " << m_idSpanMap.size() << std::endl;
	for(const auto& t : m_idSpanMap)
	{
		std::cout << "页号：" << t.first << std::endl;
		std::cout << "链表指针：" << t.second->freeList << "\t" << ((size_t)t.second->freeList >> PAGE_SHIFT) <<std::endl;
		std::cout << "是否使用：" << t.second->isUsed << std::endl;
		std::cout << "页的数量：" << t.second->n << std::endl;
		std::cout << "切好内存的大小：" << t.second->objSize << std::endl;
		std::cout << "起始页号：" << t.second->pageId << std::endl;
		std::cout << "小内存使用数量：" << t.second->useCount << std::endl;
		std::cout << "next：" << t.second->next << std::endl;
		std::cout << "prev：" << t.second->prev << std::endl;
		std::cout << "-----------------------------------------" << std::endl;

	}
	std::cout << "+++++++++++++++++++++++++++++++++++++++" << std::endl;
}